The present invention relates to networks, and more particularly to selecting data for transmission in networks.
Data transmission in networks may be subjected to some bandwidth (i.e., bits-per-second) requirements. For example, on a voice channel, data may have to be transmitted at exactly 64 Kbps. In another example, a network user may have contracted with a network service provider for a minimum and maximum bandwidth parameters. The network provider must limit the user""s data rates to these bandwidth parameters.
FIG. 1 illustrates a scheduler that selects (schedules) data for transmission in accordance with predefined bandwidth parameters. The scheduler is used in an asynchronous transfer mode (ATM) switch. The scheduler schedules data transmission on virtual connections (VCs) 120 which share an output port 130. Each VC is to be given some bandwidth which is a portion of the total bandwidth of port 130. The bandwidth of each VC is defined by a parameter xcex94 (a separate parameter for each VC). xcex94 is the number of cell times in which a single ATM cell must be transmitted on the VC. xcex94 can be thought of as the time between transmission of consecutive cells on the VC.
The scheduling method can be conceptually represented using a time wheel 140. The time wheel has a number of time slots 150.0, 150.1, 150.2, 150.3. . . Each of these time slots 150 is associated with a queue 160 of virtual connections 120 which should transmit a cell at the same time in order to meet their respective bandwidth parameters xcex94. However, only one VC can transmit on port 130 at any given time.
Each cell time, the time wheel rotates clockwise by one time slot. Hence, the queue 160 of slot 150.2 moves to slot 150.1, the queue 160 of slot 150.3 moves to slot 150.2, and so on. When a queue 160 reaches slot 150.0, its VCs are added to active queue 160.0. The active queue contains VCs that should transmit in the current cell time. One VC is dequeued from the head of the active queue. This VC is shown at 120.0 in FIG. 1. A cell is transmitted from this VC to port 130. Then the VC 120.0 is moved to the queue 160 in time wheel slot xcex94 (i.e., slot 150.xcex94) where xcex94 is the bandwidth parameter of the VC 120.0. This means the VC will return to the active queue in xcex94 cell times, which is when the next cell on the VC should be transmitted.
When a VC 120 is added to active queue 160.0, the VC may have to wait for other VCs ahead in the queue before a cell from the VC is transmitted. If VC 120.0 has waited for xe2x80x9cdxe2x80x9d cell times, the VC is moved to queue xcex94xe2x88x92d (i.e., queue of slot xcex94xe2x88x92d) rather than xcex94. Therefore, the VC will re-enter the active queue 160.0 xe2x80x9cdxe2x80x9dcell times earlier.
In one implementation, a Current_Time counter keeps the current time, measured in cell times. Each VC 120 is associated with a time stamp register TS storing the time when the next cell should be transmitted on the VC. When a cell is transmitted on the VC, the corresponding TS is incremented by xcex94. Then the VC is moved to queue Q_Id=TSxe2x88x92Current_Time. Since TS and xcex94 can be fractional numbers, Q_Id is actually computed as int (TS)xe2x88x92Current_Time, where xe2x80x9cintxe2x80x9d is a function equal to the largest integer not exceeding the argument TS. See European patent application EP 0 874 531xe2x80x9cATM Cell Scheduling Methodxe2x80x9d filed by MMC Networks, Inc. (published Oct. 28, 1998). See also xe2x80x9cAF5500 Chip Set User Guidexe2x80x9d (MMC Networks, Inc. of Sunnyvale, Calif. July 1998), pages 8-1 through 8-40.
Improvements on this scheme are desirable.
The inventor has observed that if the total bandwidth of port 130 is high but the minimal supportable bandwidth for an individual VC is allowed to be low, the cell scheduling method of FIG. 1 can require a large number of queues 160. The number of queues required is determined by the maximum value of the xcex94 parameters. This is because when a cell is transmitted on a VC, the VC can be returned to the queue number xcex94 to allow the next cell transmission in xcex94 time slots. It can be shown that the maximum value of xcex94 is the ratio TB/mb, where TB is the total bandwidth of port 130 and mb is the minimum bandwidth supported by the ATM switch (here the bandwidth is measured in bits per second). For example, if port 130 is an optical carrier OC-192 port (9953.280 Mbps) and xe2x80x9cmbxe2x80x9d represents a DSO voice channel (64 Kbps), the number of queues required is 9953280/64=155520. This large number of queues requires a large memory. The large memory increases the size, cost and power dissipation of the switch.
In one scheduler of the present invention, the number of queues required is reduced exponentially to about log (max xcex94) where xe2x80x9clogxe2x80x9d is a logarithm base 2 and xe2x80x9cmax xcex94xe2x80x9d is the maximum value of xcex94. The scheduler works as follows. Let the non-active queues be denoted as Q1, Q2, . . . QN, where N is the number of queues. N is ┌log (max xcex94)┐, i.e., log (max xcex94) rounded up to an integer. VCs are transferred from queue Q1 to the active queue every second cell time, from queue Q2 to the active queue every fourth cell time, from queue Q3 to the active queue every eighth cell time, and so on. VCs are transferred from queue Qi to the active queue every 2ith cell time.
As in FIG. 1, one VC is selected from the active queue for transmission every cell time. A cell is transmitted on the VC and the VC is moved to the queue Qi, where the queue number i=log xcex94, rounded to an integer. If the VC has waited in the active queue for xe2x80x9cdxe2x80x9d cell times, then i=log (xcex94xe2x88x92d), rounded to an integer.
The invention is not limited to the embodiments described above. Queues Qi and the active queue can be replaced with non-queue data structures. The invention can be applied to non-ATM networks. The invention can be applied to data flows other than VCs. Other embodiments and variations are within the scope of the invention, as defined by the appended claims.